package primary.primary0;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 注意他是不重复的，全排列2是可重复的
 */
public class S0046全排列 {


    /**
     * 回溯
     * 每层给上一层留下的result里的每一个，添加剩下的nums中的一个，变成一个新的result，传下去
     * 然后再删了，换另一个值添加，传下去
     * 每个节点判断当前用完了的话就添加到result里面去
     */

    /**
     * 层序遍历会感觉有点恶心
     * mark:一层层处理的话，用swap会流畅一些
     */


    /**
     * 86
     * 注意它本来就是不重复的，那就回溯吧，用一个visited矩阵来判断每个点是否被用过
     * 回溯好像不行，我就一个字母一个字母地加吧。
     * 比如前n个数字构成了k个，那么第n+1个数字，就会对之前k个List中的每一个，创造出n+1个新的List，
     * 并且这样创建的 n+1 * k 个list是不会有重复的，因为本来的k个是不重复的。
     * 从公式上也符合全排列A(n,0) = n*(n-1)*...*1
     */
    class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null || nums.length == 0){
                return res;
            }
            int totalLen = nums.length;
            List<Integer> initList = new ArrayList<>();
            initList.add(nums[0]);
            res.add(initList);

            for(int i = 1; i < totalLen; i++){
                List<List<Integer>> resTemp = new ArrayList<>();
                for(int m = 0; m < res.size(); m++){
                    List<Integer> curList = res.get(m);
                    // mark: List截取api要熟练
                    for(int j = 0; j <= i; j++){
                        resTemp.add(insetNumIntoList(curList, nums[i], j));
                    }
                }
                res = resTemp;
            }
            return res;
        }

        public List<Integer> insetNumIntoList(List<Integer> inputList, int k, int loc){
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i < inputList.size(); i++){
                if(i == loc){
                    res.add(k);
                }
                res.add(inputList.get(i));
            }
            if(loc == inputList.size()){
                res.add(k);
            }
            return res;
        }
    }



    /**
     * 86
     * 看了答案的想法，试一下回溯。
     * 逐个塞值，然后每次塞的时候判断这个值是否被塞过。这种一个个挑选的题目就很像回溯。
     * 我本来以为回溯，判断哪些点用过的时候，每判断一次都需要轮询整个visited数组，这个开销很大
     * 实际上，虽然确实是每一次都是判断一整个visited，但是开销也还好。
     */
    class Solution2{
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null || nums.length == 0){
                return res;
            }
            boolean[] visited = new boolean[nums.length];
            List<Integer> curPath = new ArrayList<>();
            permuteHelp(nums, 0, visited, res, curPath);
            return res;
        }

        public void permuteHelp(int[] nums, int curLoc, boolean[] visited, List<List<Integer>> res, List<Integer> curPath){
            if(curLoc == nums.length){
                res.add(cloneList(curPath));
                return;
            }
            for(int i = 0; i < nums.length; i++){
                if(!visited[i]){
                    visited[i] = true;
                    curPath.add(nums[i]);
                    permuteHelp(nums, curLoc + 1, visited, res, curPath);
                    curPath.remove(curPath.size() - 1);
                    visited[i] = false;
                }
            }
        }

        public List<Integer> cloneList(List<Integer> input){
            List<Integer> res = new ArrayList<>();
            for(Integer i : input){
                res.add(i);
            }
            return res;
        }

        /**
         * List的拷贝
         */
        public List<Integer> cloneList2(List<Integer> input){
            return new ArrayList<Integer>(input);
        }
    }


    /**
     * 答案的, 通过交换，这样就不用判断每个数字是否被用过了。
     * 其实就是在每个位置填一下每一种值，但是你不用考虑之前的，因为之前的在往后换的时候已经给你填过了
     */
    class Solution3 {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();

            List<Integer> output = new ArrayList<Integer>();
            for (int num : nums) {
                output.add(num);
            }

            int n = nums.length;
            backtrack(n, output, res, 0);
            return res;
        }

        public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
            // 所有数都填完了
            if (first == n) {
                // 一定要在n的时候才去处理，虽然中间的也能处理，但是这样的话会需要去重，所以只看n
                res.add(new ArrayList<Integer>(output));
            }
            // 这个时候，不包括first 的 frist之前的每一个数，其实都被用过了
            // 即使当前output的前first位，它是乱序的，也是这样。
            // mark: 精妙
            for (int i = first; i < n; i++) {
                // 动态维护数组
                Collections.swap(output, first, i);
                // 继续递归填下一个数
                backtrack(n, output, res, first + 1);
                // 撤销操作
                Collections.swap(output, first, i);
            }
        }
    }

}
